package my.algorithms.sort;

public class QuickSort
{
	/**
	 * 
	 * @param arr
	 *            the array we're sorting in place
	 * @param left
	 *            the left most element we'll look at
	 * @param right
	 *            the right most element we'll look at
	 * @return the index where left and right met
	 */
	int partition(int arr[], int left, int right)
	{
		
		int i = left, j = right;
		int tmp;
		// for large numbers this could cause a buffer overflow
		int pivot = arr[(left + right) / 2];

		// while the left pointer is less than the right
		while (i <= j)
		{
			// while the left position is less than the pivot value, leave them alone
			//   there's no need to move it
			while (arr[i] < pivot)
				i++;
			// while the right position is less than the pivot value, leave them alone
			//   there's no need to move it
			while (arr[j] > pivot)
				j--;
			// if we're still not overlapping swamp
			if (i <= j)
			{
				// at this point we know both i and j represent i >= pivot <= j, so swap them in place
				tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
				i++;
				j--;
			}
		};
		return i;
	}

	void quickSort(int arr[], int left, int right)
	{
		// the index where the left ptr met the right ptr
		int index = partition(arr, left, right);
		
		// if the left is less than the index of the last sort continue
		if (left < index - 1)
			quickSort(arr, left, index - 1);
		// if the index of the last sort is less than the right then continue
		if (index < right)
			quickSort(arr, index, right);
	}

}
